Discrete Mathematics
Q71.
A given connected graph G is a Euler Graph if and only if all vertices of G are ofQ72.
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x \in V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)-d(v)?Q73.
Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is _________.Q74.
A cube of side 1 unit is placed in such a way that the origin coincides with one of its top vertices and the three axes along three of its edges. What are the co-ordinates of the vertex which is diagonally opposite to the vertex whose co-ordinates are (1, 0, 1)?Q75.
If G is a forest with n vertices and k connected components, how many edges does G have?Q78.
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?Q79.
The conic section that is obtained when a right circular cone is cut through a plane that is parallel to the side of the cone is called _____Q80.
An ordered n-tuple (d_{1}, d_{2} ,... , d_{n}) with d_{1}\geq d_{2} \geq ... \geq d_{n} is called graphic if there exists a simple undirected graph with n vertices having degrees d_{1}, d_{2} ,... , d_{n} respectively. Which of the following 6-tuples is NOT graphic?